A computer system includes a number of separate components such as memory, processors (CPUs), and input/output devices. All of these components must be able to communicate with each other. The most common conventional means of intercommunication has been by the use of buses and crossbars.
Recent advancements in the electronics industry are causing bus and crossbar interconnect techniques to be insufficient. Very large scale integration (VLSI) makes it possible to form a small, low speed processor on a single chip. It is now therefore cost effective to construct a large, high speed processor by ganging many single chip processors. When this is done, however, the interconnect between the processors becomes a major bottleneck in attempting to increase the overall efficiency of the processor.
Ideally, the interconnect must be able to supply sufficient bandwidth and to connect a large number of processors together at a reasonable cost. It is also highly desirable that the interconnect be expandable, as by adding processors to increase system power. While expanding the network with further processors or devices, it is desirable that the interconnect bandwith expands with it without excessive cost and without a required purchase of initially unneeded hardware to support the future expansion.
Conventional bus and crossbar interconnection techniques do not meet these requirements. A bus has only electrical limitations on the number of processors it can service, but has a fixed bandwidth. The bandwidth of a crossbar increases with the number of processors which it interconnects, but its cost grows as the square of the number of processors and is not expandable at all without initial overdesign.
In local area computer networks, the bandwidth requirements are usually low enough that a bus will suffice, but buses are not fault tolerant. Failure of the bus will cause failure of the entire network. A crossbar is generally not feasible for a local area computer network because of the N.sup.2 cost growth relation. The fault tolerance of a crossbar is only slightly greater than the fault tolerance of a bus, as each pair of nodes inside a crossbar has only a single link between them. Therefore, failure of the link prevents any communication between the two nodes in the crossbar. Neither crossbar nor bus interconnection techniques allow local area computer networks to be easily expandable for the reasons discussed above.
More recently, expandability and fault tolerance have been somewhat imperfectly achieved by the employment of packet-switching, rather than circuit-switching, techniques. In packet switching, a user's logical message is separated (disassembled) and transmitted in multiple user packets. The packet may contain user data and control data, all of which are switched as a composite whole. Each packet of the user data generally contains a header that has information as to the packet's final destination.
Packet switching often is used in a multinode system with several alternative paths between the origin of a packet and its final destination. The use of packet switching and multiple communication paths allows the bypassing of failed switches or lines and, where packet switching control is distributed at each node, allows expansion of the system without initial overdesign. However, the control software of such nodes has generally not been flexible in adapting to faults in the network.
Packet switching in a multinode interconnect system has other problems as well. One of these is load balancing. Where routing rules are chosen such that a packet is sent on the path requiring the least nodal travel distance to reach its destination, often certain paths are selected at a much greater frequency than other paths, causing an imbalance of loading on the system and possible static deadlock. Another problem found in multinode packet switching systems is dynamic deadlock. Dynamic deadlock is caused when a node "forces" a packet out of the node in order to free a pocket storage buffer for the receipt of another packet. The packet may be forced out along an output line that moves it away from the packet's destination. With a poor set of routing rules, the packet may circulate endlessly, resulting in dynamic deadlock.
Therefore, a need has arisen for a multinode packet switching network which has a minimum logical distance between nodes and that is operated by a set of routing rules to prevent static and dynamic deadlock. Further, a need exists for a packet switching network that is extremely fault tolerant and provides a self-repairing distributed control over the packet switching function.